The present invention relates to low density parity check (LDPC) codes, and more particularly, to methods and system designs for efficiently storing LDPC matrices typically used in WiMAX, 802.11n, and other communication systems.
LDPC codes have become one of the hottest topics in current coding theory. First appearing around the middle of the twentieth century, LDPC codes have experienced an amazing comeback in the last few years since they are already equipped with very fast (probabilistic) encoding and decoding algorithms. Recovering the original codeword in the face of large amounts of noise was previously the most important issue, however, new analytic and combinatorial tools make it possible to solve related design problems. As a result, LDPC codes are not only attractive from a theoretical point of view, but also suitable for practical applications.
Regarding implementation of encoding (or decoding) LDPC codes using a generator matrix, storing a very large matrix is required according to the related art, where LDPC codes typically require large blocks of a matrix to be effective and ready for use, so as to achieve better performance. Consequently, even though parity check matrices of LDPC codes may be sparse in some occasions, how to store these matrices in a cost-effective manner without hindering the performance is still a thorny problem for developers and researchers.
Please refer to FIG. 1. FIG. 1 illustrates a parity check matrix H of LDPC codes according to the related art, where a subscript aj, k of an element of the parity check matrix H may represent a shifting number i (which is typically a non-negative integer as known by those skilled in the related art), so this element can be referred to as Pi. Typically, each of a plurality of elements of the parity check matrix H is defined as a cyclic permutation matrix of a size L by L, with L representing a sub-block size, which is a sub-matrix size for the parity check matrix H. As shown in FIG. 2, FIG. 3, and FIG. 4, some examples of cyclic permutation matrices Pi with L=8 according to the related art are illustrated for better comprehension. Generally speaking, the cyclic permutation matrix Pi is produced by cyclically shifting columns of an identity matrix to the right by i number of places, where the cyclic permutation matrix Pi is substantially the identity matrix if the shifting number i is zero.
Regarding a larger number of the sub-matrix size L, for example, L=81, if the height and the width of the parity check matrix H are respectively 12 and 24 (i.e. m=12 and c=24), the corresponding codeword block length n may reach 1944 bits (i.e. 243 bytes) and the total storage volume required for the parity check matrix H may reach 2916 bytes. It is noted that storing different parity check matrices corresponding to various conditions (e.g. various code rates or various transmission parameters) is typically required according to the related art. Therefore, storage requirements for these parity check matrices have become an important issue.